import java.util.ArrayList;
import java.util.List;

public class T8螺旋矩阵 {

    public static void main(String[] args) {
        int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};
        System.out.println(spiralOrder(matrix));
    }
    private static int[][] Dirs = {{0,1},{1,0},{0,-1},{-1,0}};//右下左上

    public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ret = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0;
        int j = 0;
        int dir = 0;//方向
        for(int k=0;k<m*n;k++) {
            ret.add(matrix[i][j]);
            matrix[i][j] = Integer.MAX_VALUE;//标记遍历了
            //判断是否需要换方向
            int x = i + Dirs[dir][0];
            int y = j + Dirs[dir][1];//这两个只用于判断，真正的加入结果中还是i，j
            if(x<0 || x>=m || y<0 || y>=n || matrix[x][y]==Integer.MAX_VALUE) {
                dir = (dir+1) % 4;
            }
            //走一步
            i += Dirs[dir][0];
            j += Dirs[dir][1];
        }
        return ret;
    }
}
